{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2, Topic 1: Fault Attack on RSA (MAIN)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Acknowledgements\n",
    "\n",
    "This attack is was originally detailed in a [1997 paper by Boneh, Demillo, and Lipton](https://www.researchgate.net/publication/2409434_On_the_Importance_of_Checking_Computations). This tutorial draws heavily from a blog post by David Wong, which you can find [here](https://www.cryptologie.net/article/371/fault-attacks-on-rsas-signatures/)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "NOTE: This lab references some (commercial) training material on [ChipWhisperer.io](https://www.ChipWhisperer.io). You can freely execute and use the lab per the open-source license (including using it in your own courses if you distribute similarly), but you must maintain notice about this source location. Consider joining our training course to enjoy the full experience.\n",
    "\n",
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**SUMMARY:** *So far, we've seen how clock and voltage glitches can be used to disrupt a microcontroller or FPGA, potentially changing the execution path. We've also seen that, in the case of AES, if we disrupt the calculation in a certian spot only twice, we can easily recover a quarter of the key bytes.*\n",
    "\n",
    "*In this lab, we'll explore an attack on RSA, more specifically an RSA optimization, that can recover the entire key with a single fault.*\n",
    "\n",
    "**LEARNING OUTCOMES:**\n",
    "\n",
    "* Understanding conditions for the fault\n",
    "* Recovering an RSA private key from a faulty signature"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Attack Theory\n",
    "\n",
    "The theory for this attack is a bit simpler than the one for AES, so we'll take you through it here instead of putting it in another notebook. If you don't know, RSA is an asymmetric cryptographic algorithm, meaning it has a public and private key, with one being used for encryption and the other for decryption. It can be used in both a public encryption/private decryption configuration and a private encryption/public decryption situation. We'll be attacking the latter case. Let's assume that the target is signing a message and is sending it to us so we can verify the identity of the device.\n",
    "\n",
    "For RSA, the public key is made up of two numbers, $n$ and $e$. The private key is made up of $n$ and $d$. These numbers have some special properties:\n",
    "\n",
    "1. $n$ is constructed as the product of 2 prime numbers, $p$ and $q$.\n",
    "1. $d$ is derived from $p$, $q$, and $e$.\n",
    "\n",
    "As a result of these properties, a few things are evident:\n",
    "\n",
    "1. If we learn $p$ or $q$, we can derive the other prime number since $n$ is public information.\n",
    "1. If we learn $p$ and $q$, we can derive $d$ since $e$ is public information.\n",
    "\n",
    "The target can encrypt/sign a message with the following equation ($s$ is the signature and $m$ is the message):\n",
    "\n",
    "$$s = m^d({mod}\\space n)$$\n",
    "\n",
    "And we can decrypt/verify the message with the following equation:\n",
    "\n",
    "$$s^e = m(mod\\space n)$$\n",
    "\n",
    "One issue with RSA is that it's very slow - these equations are simple, but they use massive numbers; if the numbers used are too small, it's trivial for a computer to factor $n$ into $p$ and $q$. $n$ for the firmware we're attacking is 1024 bits long, which is on the smaller size of secure keys at this point. This encryption/signing operation is especially slow.\n",
    "\n",
    "An important property of the signature verification equation is that the following is also true:\n",
    "\n",
    "$$(m - s^e)(mod\\space n) = 0$$\n",
    "\n",
    "aka $(m - s^e)$ is divisible by $n$. It follows that $(m - s^e)$ is divisible by $p$ and $q$ as well.\n",
    "\n",
    "## The Chinese Remainder Theorem (CRT)\n",
    "\n",
    "To help speed up the encryption, an optimization known as the Chinese Remainder Theorem (CRT) can be used. This theorem allows us derive two new exponents, $d_p$ and $d_q$, which are much smaller than $d$. We can then replace\n",
    "\n",
    "$$s = m^d({mod}\\space n)$$\n",
    "\n",
    "with two equations\n",
    "\n",
    "$$s_1 = m^{d_p}(mod\\ p) \\\\\n",
    "s_2 = m^{d_q}(mod\\ q)$$\n",
    "\n",
    "$s$ is then:\n",
    "\n",
    "$$i_q = q^{-1}mod\\ p \\\\\n",
    "s = s_2 + q(i_q(s_1 - s_2)mod\\ p)\n",
    "$$\n",
    "\n",
    "$s_1$ and $s_2$ can be combined into $s$ via CRT. Even though there's two modular exponentiations, this is still much faster since $d_p$ and $d_q$ are much smaller than $d$ and $p$ and $q$ are much smaller than $n$. This is the optimization that our target, which is using a slightly modified version of MBEDTLS (more on that in a bit), makes.\n",
    "\n",
    "## Inserting a Fault\n",
    "\n",
    "Suppose that instead of everything going smoothly as above, a fault happens during the calculation of $s_2$, turning it into $s'_2$. $s_1$ and $s'_2$ will then be combined into $s'$. If that happens, a couple of things will be true:\n",
    "\n",
    "1. When we go to verify the signature, it won't work: $s'^e \\neq m (mod\\ n)$. Concequently, $(m - s'^e)(mod\\space n) \\neq 0$, so $(m - s'^e)$ is not divisible by $n$\n",
    "1. Since $(m - s'^e)$ is not divisible by $n$, it cannot be divisible by both $p$ and $q$ anymore. Due to how the CRT works, it will still be divisible by $p$, but not by $q$. This can be expressed as $(m - s'^e) = pk$ for some integer $k$.  \n",
    "1. We now have $(m - s'^e) = pk$ and $n = pq$. This means that we can find $p$ by computing $gcd(m-s'^e, n)$\n",
    "    \n",
    "Once we have $p$, we can compute $q = \\frac{n}{p}$ and $d$ via the rest of the RSA key generation algorithm. \n",
    "\n",
    "The math is similar in the case that $s_1$ is faulted, with the only difference being that we recover $q$ at the end instead of $p$.\n",
    "\n",
    "## Communicating with the Target\n",
    "\n",
    "With the math out of the way, we can get to attacking the target:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "SCOPETYPE = 'OPENADC'\n",
    "PLATFORM = 'CW308_SAM4S'\n",
    "SS_VER='SS_VER_1_1'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%run \"../../Setup_Scripts/Setup_Generic.ipynb\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%bash -s \"$PLATFORM\" \"$SS_VER\"\n",
    "cd ../../../firmware/mcu/simpleserial-rsa\n",
    "make PLATFORM=$1 CRYPTO_TARGET=MBEDTLS CRYPTO_OPTIONS=RSA OPT=2 SS_VER=$2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cw.target_logger.setLevel(cw.logging.WARNING)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "fw_path = \"../../../firmware/mcu/simpleserial-rsa/simpleserial-rsa-{}.hex\".format(PLATFORM)\n",
    "cw.program_target(scope, prog, fw_path)\n",
    "time.sleep(1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This target is using the simpleserial protocol, but the full signature is too big to read back in a single command. This means we instead read back the signature in 3 commands:\n",
    "\n",
    "1. `'t'` will do the signature calculation and respond with the first 48 bytes of the signature\n",
    "1. `'1'` will return the next 48 bytes of the signature\n",
    "1. `'2'` will return the final 32 bytes of the signature"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "scope.clock.adc_src = \"clkgen_x1\"\n",
    "reset_target(scope)\n",
    "target.flush()\n",
    "scope.arm()\n",
    "target.simpleserial_write(\"t\", bytearray([]))\n",
    "    \n",
    "ret = scope.capture()\n",
    "if ret:\n",
    "    print('Timeout happened during acquisition')\n",
    "    \n",
    "time.sleep(2)\n",
    "if SS_VER=='SS_VER_2_1':\n",
    "    output = target.simpleserial_read_witherrors('r', 128, timeout=1)\n",
    "else:\n",
    "    output = target.simpleserial_read_witherrors('r', 48, timeout=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sig = None\n",
    "if output['valid']:\n",
    "    print(output['payload'])\n",
    "    sig = output['payload']\n",
    "    \n",
    "print(scope.adc.trig_count)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "That took a long time, probably more than 10M cycles! Let's read back the rest of the message and append it to our signature:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if SS_VER!='SS_VER_2_1':\n",
    "    target.simpleserial_write(\"1\", bytearray())\n",
    "    time.sleep(0.2)\n",
    "    output = target.simpleserial_read_witherrors('r', 48, timeout=10)\n",
    "    if output['valid']:\n",
    "        sig.extend(output['payload'])\n",
    "\n",
    "    target.simpleserial_write(\"2\", bytearray())\n",
    "    time.sleep(0.2)\n",
    "    output = target.simpleserial_read_witherrors('r', 32, timeout=10)\n",
    "    if output['valid']:\n",
    "        sig.extend(output['payload'])\n",
    "\n",
    "    print(sig)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if PLATFORM == \"CWLITEXMEGA\":\n",
    "    def reboot_flush():            \n",
    "        scope.io.pdic = False\n",
    "        time.sleep(0.1)\n",
    "        scope.io.pdic = \"high_z\"\n",
    "        time.sleep(0.1)\n",
    "        #Flush garbage too\n",
    "        target.flush()\n",
    "else:\n",
    "    def reboot_flush():            \n",
    "        scope.io.nrst = False\n",
    "        time.sleep(0.05)\n",
    "        scope.io.nrst = \"high_z\"\n",
    "        time.sleep(0.05)\n",
    "        #Flush garbage too\n",
    "        target.flush()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's verify that our signature is correct and that we can verify it:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.PublicKey import RSA\n",
    "from Crypto.Signature import PKCS1_v1_5 \n",
    "\n",
    "from Crypto.Hash import SHA256\n",
    "\n",
    "e = 0x10001\n",
    "n = 0x9292758453063D803DD603D5E777D7888ED1D5BF35786190FA2F23EBC0848AEADDA92CA6C3D80B32C4D109BE0F36D6AE7130B9CED7ACDF54CFC7555AC14EEBAB93A89813FBF3C4F8066D2D800F7C38A81AE31942917403FF4946B0A83D3D3E05EE57C6F5F5606FB5D4BC6CD34EE0801A5E94BB77B07507233A0BC7BAC8F90F79\n",
    "m = b\"Hello World!\"\n",
    "\n",
    "hash_object = SHA256.new(data=m)\n",
    "pub_key = RSA.construct((n, e))\n",
    "signer = PKCS1_v1_5.new(pub_key) \n",
    "sig_check = signer.verify(hash_object, sig)\n",
    "print(sig_check)\n",
    "\n",
    "assert sig_check, \"Failed to verify signature on device. Got: {}\".format(newout)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's setup the glitch module. Use settings here that worked for you before. Ideally, you'll have a single group of settings here - RSA is very slow (as you've seen), so trying to scan settings here would take forever!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "if scope._is_husky:\n",
    "    scope.glitch.enabled = True\n",
    "scope.glitch.clk_src = \"clkgen\"\n",
    "scope.glitch.output = \"clock_xor\"\n",
    "scope.glitch.trigger_src = \"ext_single\"\n",
    "scope.glitch.repeat = 1\n",
    "# These width/offset numbers are for CW-Lite/Pro; for CW-Husky, convert as per Fault 1_1:\n",
    "scope.glitch.width = -9\n",
    "scope.glitch.offset = -38.3\n",
    "scope.io.hs2 = \"glitch\"\n",
    "print(scope.glitch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tqdm.notebook import trange\n",
    "import time\n",
    "for i in trange(7000000, 7100000): #look for something kind of near the end\n",
    "    scope.glitch.ext_offset = i\n",
    "    scope.adc.timeout = 3\n",
    "    target.flush()\n",
    "    scope.arm()\n",
    "    target.simpleserial_write(\"t\", bytearray([]))\n",
    "\n",
    "    ret = scope.capture()\n",
    "    if ret:\n",
    "        print('Timeout happened during acquisition')\n",
    "\n",
    "    time.sleep(2)\n",
    "    if SS_VER=='SS_VER_2_0':\n",
    "        output = target.simpleserial_read_witherrors('r', 128, timeout=100, glitch_timeout=1)\n",
    "    else: \n",
    "        output = target.simpleserial_read_witherrors('r', 48, timeout=100, glitch_timeout=1)\n",
    "    if invalid_output: # replace with invalid output detection\n",
    "        print(\"crash\") #we can't really do anything here - we need the full signature back\n",
    "    else:\n",
    "        if glitched_output: #detect if the calculation was messed up\n",
    "            # call the faulty signature whatever you want\n",
    "            # but we'll assume it's called sig for the rest of the lab\n",
    "            sig = \n",
    "        else:\n",
    "            pass # normal operation, nothing special"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Padding the Message\n",
    "\n",
    "We've got our glitched signature, but we've still got a little work to do. The $m$ isn't actually the message by itself. Instead, it's a PKCS#1 v1.5 padded hash of it. Luckily, this standard's fairly simple. PKCS#1 v1.5 padding looks like:\n",
    "\n",
    "\\|00\\|01\\|ff...\\|00\\|hash_prefix\\|message_hash\\|\n",
    "\n",
    "Here, the ff... part is a string of ff bytes long enough to make the size of the padded message the same as N, while hash_prefix is an identifier number for the hash algorithm used on message_hash. Our message was hashed using SHA256, which has the hash prefix `3031300d060960864801650304020105000420`.\n",
    "\n",
    "We can get our hashed message and $m$ with the following code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.Hash import SHA256\n",
    "from binascii import hexlify, unhexlify\n",
    "\n",
    "def build_message(m, n):\n",
    "    sha_id = \"3031300d060960864801650304020105000420\"\n",
    "    N_len = (len(bin(n)) - 2 + 7) // 8\n",
    "    pad_len = (len(hex(n)) - 2) // 2 - 3 - len(m)//2 - len(sha_id)//2\n",
    "    padded_m = \"0001\" + \"ff\" * pad_len + \"00\" + sha_id + m\n",
    "    return padded_m\n",
    "\n",
    "hashed_m = hexlify(hash_object.digest()).decode()\n",
    "padded_m = build_message(hashed_m, n)\n",
    "print(hashed_m)\n",
    "print(padded_m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Recovering the Private Key\n",
    "\n",
    "Now we can recover the private values by plugging them into the equations from earlier. If you can, install the gmpy2 Python library, which has much better support for big integer math like this. Otherwise, run the next block and wait for a few minutes for the calculation to finish.\n",
    "\n",
    "You can get gmpy2 on Windows from the following link: https://pypi.org/project/gmpy2/#files. On Linux, you can install it via your package manager (python3-gmpy2 on Apt, for example)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd\n",
    "n = 0x9292758453063D803DD603D5E777D7888ED1D5BF35786190FA2F23EBC0848AEADDA92CA6C3D80B32C4D109BE0F36D6AE7130B9CED7ACDF54CFC7555AC14EEBAB93A89813FBF3C4F8066D2D800F7C38A81AE31942917403FF4946B0A83D3D3E05EE57C6F5F5606FB5D4BC6CD34EE0801A5E94BB77B07507233A0BC7BAC8F90F79\n",
    "e = 0x10001\n",
    "try:\n",
    "    import gmpy2\n",
    "    from gmpy2 import mpz\n",
    "    sig_int = mpz(int.from_bytes(sig, \"big\"))\n",
    "    m_int = mpz(int.from_bytes(unhexlify(padded_m), \"big\"))\n",
    "    p_test = gmpy2.gcd(???)\n",
    "except (ImportError, ModuleNotFoundError) as error:\n",
    "    print(\"gmpy2 not found, falling back to Python\")\n",
    "    sig_int = int.from_bytes(sig, \"big\")\n",
    "    padded_m_int = int.from_bytes(unhexlify(padded_m), \"big\")\n",
    "    p_test = gcd(???)\n",
    "    \n",
    "print(hex(p_test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We should now have either $p$ or $q$! We can get the other prime by simply dividing $n$ by the one we have."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "q_test = n//p_test\n",
    "print(hex(q_test))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The $d$ calculation is a bit more complicated. Here's some code to derive it from $q$, $p$, and $e$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "phi = (q_test - 1)*(p_test - 1)\n",
    "def egcd(a, b):\n",
    "    x,y, u,v = 0,1, 1,0\n",
    "    while a != 0:\n",
    "        q, r = b//a, b%a\n",
    "        m, n = x-u*q, y-v*q\n",
    "        b,a, x,y, u,v = a,r, u,v, m,n\n",
    "        gcd = b\n",
    "    return gcd, x, y\n",
    "\n",
    "gcd, d, b = egcd(e, phi)\n",
    "\n",
    "print(hex(d))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's sign the original message and see if we can verify it with our original verifier:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Crypto.PublicKey import RSA\n",
    "from Crypto.Signature import PKCS1_v1_5 \n",
    "\n",
    "from Crypto.Hash import SHA256\n",
    "\n",
    "private_key = RSA.construct((n, e, int(d), int(p_test), int(q_test)))\n",
    "private_signer = PKCS1_v1_5.new(private_key) \n",
    "new_sig = private_signer.sign(hash_object)\n",
    "print(sig)\n",
    "\n",
    "new_sig_check = signer.verify(hash_object, new_sig)\n",
    "print(new_sig_check)\n",
    "\n",
    "assert new_sig_check, \"Failed to verify signature on device. Got: {}\".format(newout)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that you've seen the attack work, you might want to try doing the falut in the other half of the RSA calculation to see if you can get the other prime number back."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Caveats to the Attack\n",
    "\n",
    "The crypto implementation we're attack isn't actually vulnerable to this attack without some additional glitching. This is because it verifies the signature is valid before sending it off. With a more complicated glitch setup, we could try glitching past it, but this is outside the scope of this lab. Some ideas include modifying the ChipWhisperer FPGA code to generate a second glitch, using a second ChipWhisperer (easiest if you were voltage glitching), and using a second trigger and trying to rearm between the two signature encryptions. You might even be able to increase the repeat and glitch near the end of the second encryption algorithm to glitch past both.\n",
    "\n",
    "Instead though, we copied some of the functions and commented out the following signature check:\n",
    "\n",
    "```C\n",
    "    /* Compare in constant time just in case */\n",
    "    for( diff = 0, i = 0; i < ctx->len; i++ )\n",
    "        diff |= verif[i] ^ sig[i];\n",
    "    diff_no_optimize = diff;\n",
    "\n",
    "    if( diff_no_optimize != 0 )\n",
    "    {\n",
    "        ret = MBEDTLS_ERR_RSA_PRIVATE_FAILED;\n",
    "        goto cleanup;\n",
    "    }\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Conclusions & Next Steps\n",
    "\n",
    "You've seen in previous labs that there are very powerful fault attacks on symmetric cryptographic algorithms that can be used to recover an AES key with a few faults. From this one, you've seen an even more powerful attack is possible on the asymmetric cryptographic algorithm RSA-CRT that can recover the plaintext in a single fault. "
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
